关于大量数据查找，效率差距到底有多大？

先看一组实例：

输出结果为：

对于大数据集量来说，我们清晰地看到，集合的查找效率远远的高于列表，那么本文接下来会从Python底层数据结构的角度分析为何出现如此情况。

Python中的list作为一个常用数据结构，在很多程序中被用来当做数组使用，可能很多人都觉得list无非就是一个动态数组，就像C++中的vector或者Go中的slice一样。但事实真的是这样的吗？

我们来思考一个简单的问题，Python中的list允许我们存储不同类型的数据，既然类型不同，那内存占用空间就就不同，不同大小的数据对象又是如何存入数组中呢？

比如下面的代码中，我们分别在数组中存储了一个字符串，一个整形，以及一个字典对象，假如是数组实现，则需要将数据存储在相邻的内存空间中，而索引访问就变成一个相当困难的事情了，毕竟我们无法猜测每个元素的大小，从而无法定位想要的元素位置。

是通过链表结构实现的吗？毕竟链表支持动态的调整，借助于指针可以引用不同类型的数据。但是这样的话使用下标索引数据的时候，需要依赖于遍历的方式查找，O(n)的时间复杂度访问效率实在是太低。

同时使用链表的开销也较大，每个数据项除了维护本地数据指针外，还要维护一个next指针，因此还要额外分配8字节数据，同时链表分散性使其无法像数组一样利用CPU的缓存来高效的执行数据读写。

实现的细节可以从其Python的源码中找到， 定义如下：

内部list的实现的是一个C结构体，该结构体中的obitem是一个指针数组，存储了所有对象的指针数据，allocated是已分配内存的数量, PyObjectVAR_HEAD是一个宏扩展包含了更多扩展属性用于管理数组，比如引用计数以及数组大小等内容。

所以我们可以看出，用动态数组作为第一层数据结构，动态数组里存储的是指针，指向对应的数据。

既然是一个动态数组，则必然会面临一个问题，如何进行容量的管理，大部分的程序语言对于此类结构使用动态调整策略，也就是当存储容量达到一定阈值的时候，扩展容量，当存储容量低于一定的阈值的时候，缩减容量。

道理很简单，但实施起来可没那么容易，什么时候扩容，扩多少，什么时候执行回收，每次又要回收多少空闲容量，这些都是在实现过程中需要明确的问题。

假如我们使用一种最简单的策略：超出容量加倍，低于一半容量减倍。这种策略会有什么问题呢？设想一下当我们在容量已满的时候进行一次插入，随即删除该元素，交替执行多次，那数组数据岂不是会不断地被整体复制和回收，已经无性能可言了。

对于Python list的动态调整规则程序中定义如下, 当追加数据容量已满的时候，通过下面的方式计算再次分配的空间大小，创建新的数组，并将所有数据复制到新的数组中。这是一种相对数据增速较慢的策略，回收的时候则当容量空闲一半的时候执行策略，获取新的缩减后容量大小。

具体规则如下：